/*
 * Copyright (C), 2015-2018
 * FileName: Solution023
 * Author:   zhao
 * Date:     2018/11/21 20:20
 * Description: 23. 合并K个排序链表
 * History:
 * <author>          <time>          <version>          <desc>
 * 作者姓名           修改时间           版本号              描述
 */
package com.lizhaoblog.mid;

import com.lizhaoblog.diynode.ListNode;

/**
 * 〈一句话功能简述〉<br>
 * 〈23. 合并K个排序链表〉
 *
 * @author zhao
 * @date 2018/11/21 20:20
 * @since 1.0.1
 */
public class Solution023 {

    /**************************************
     * 题目
     合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

     示例:

     输入:
     [
     1->4->5,
     1->3->4,
     2->6
     ]
     输出: 1->1->2->3->4->4->5->6
     **************************************/

    /**************************************
     *
     * 想法：
     *      1. 复制 021-合并两个有序列表 的思路，去遍历lists中的每个ListNode，然后对比各项的值
     *          链接合并两个有序列表
     *          参考mergeKLists方法
     *          复杂度 n的n次方/n
     *      2. 使用两两合并的方式，左边和右边合并，
     *          参考better方法
     *          每执行一次while的循环体，需要合并的链表数就减半，因此while循环体执行次数为logk。
     *          每次执行循环体的时间开销：第一次执行循环体：k/2次合并2个长度为n的链表，
     *          时间复杂度为O(nk)；第二次执行循环体：k/4次合并2个长度为2n的链表，
     *          时间复杂度依然为O(nk)。以此类推，每次执行循环体的时间开销都为O(nk)。
     *          复杂度O(nklogk)/n
     *
     * 我的做法
     *      超过10%的测试案例
     *      复杂度：n的n次方/n
     * 代码执行过程：
     *
     * 总结：
     *      直接套用了原来的解题思路，没有开拓新的方法
     * ***********************************/
    public ListNode mergeKLists(ListNode[] lists) {

        ListNode result = new ListNode(0);
        ListNode cur = result;

        while (true) {
            Integer tmpMin = null;
            int tmpIndex = -1;
            for (int i = 0; i < lists.length; i++) {
                ListNode listNode = lists[i];
                if (listNode == null) {
                    continue;
                }
                if (tmpMin == null) {
                    tmpMin = listNode.val;
                    tmpIndex = i;
                } else {
                    if (tmpMin > listNode.val) {
                        tmpMin = listNode.val;
                        tmpIndex = i;
                    }
                }
            }
            if (tmpIndex == -1) {
                break;
            }
            cur.next = lists[tmpIndex];
            lists[tmpIndex] = lists[tmpIndex].next;
            cur = cur.next;
        }

        return result.next;
    }

    /**************************************
     * 比我好的答案 better
     * ***********************************/
    public ListNode better(ListNode[] lists) {
        if (lists.length == 0) {
            return null;
        }
        return helper(lists, 0, lists.length - 1);
    }

    private ListNode helper(ListNode[] lists, int low, int high) {
        if (low == high) {
            return lists[low];
        }
        int mid = low + (high - low) / 2;
        ListNode leftNodes = helper(lists, low, mid);
        ListNode rightNodes = helper(lists, mid + 1, high);
        return mergeTwo(leftNodes, rightNodes);

    }

    private ListNode mergeTwo(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(0);
        ListNode temp = dummy;
        while (null != list1 && null != list2) {
            if (list1.val < list2.val) {
                temp.next = list1;
                list1 = list1.next;
            } else {
                temp.next = list2;
                list2 = list2.next;
            }
            temp = temp.next;
        }
        if (null != list1) {
            temp.next = list1;
        }
        if (null != list2) {
            temp.next = list2;
        }
        return dummy.next;
    }
}
